package pri.zjy.array;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangjy
 * @description 和为 K 的子数组
 * @date 2025/6/16 16:28
 */
public class SubarraySum_560 {

    public static void main(String[] args) {
        SubarraySum_560 subarraySum560 = new SubarraySum_560();

        int[] nums = {1, 1, 1};
//        int[] nums = {1, 2, 3};
        int k = 2;
//        int k = 3;
        System.out.println(subarraySum560.subarraySum(nums, k));
    }

    /**
     * 官解：前缀和+哈希表
     * <p>
     * 分析：
     * <p>
     * 1.map存的什么？——key=所有出现过的前缀和，value=出现的次数 <br/>
     * <p>
     * 2.为什么要用map？——当遍历 j 时，可以快速找到有多少个 i，满足pre[i]=pre[j]-k，也就是pre[j]-pre[i]=k。<br/>
     * 因为现在转换为找pre[j]-k这段连续子数组，若
     */
    public int subarraySum2(int[] nums, int k) {
        // 假设preSum[i]，表示[0, i]的连续子数组的元素和；而当0<i<i+1<j，则preSum[j]为[0, j]的元素和
        // 那么[i+1, j]的连续子数组元素和 = preSum[j] - preSum[i]
        // 本题是要找出所有元素和为k的连续子数组（找满足preSum[j] - preSum[i] = k条件的所有子数组[i+1, j]），也就是preSum[j] - k = preSum[i]，即找出所有满足该条件的preSum[i]。
        // 因此，可类似两数之和，通过map记录当前的前缀和preSum[j]，以及其出现次数。这样当后面的前缀和

        // 当前元素下标是j，若map中有preSum[j]-k，意味着，[0,j]这个连续子数组中，存在一个连续子数组的元素和=k，假设[0,10]的元素和=preSum[j]-k，那么意味着[11,j]这个连续子数组的和=k

        // 假设pre[]是nums的前缀和，那么pre[i]表示[0, i]这个连续子数组的元素和；那么对于0<i<i+1<j来说，pre[j]-pre[i]的值是[i+1,j]这个连续子数组的元素和。
        // 本题要找所有元素和为k的连续子数组，也就是找出所有pre[j]-pre[i]=k的情况，假设[i+1,j]的元素和刚好等于k，所以pre[j]-k，表示[i+1,j]这个连续子数组的元素和。
        // 参考两数之和，使用map来存储当前元素期望找到的另一部分，以pre[j]为key，以前缀和出现的次数作为value；因此，本题转换为找所有pre[j]-k为key的value之和。

        // key=目前连续子数组的元素和，value=出现次数
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int preSum = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            // 记录前缀和
            preSum += nums[i];
            if (map.containsKey(preSum - k)) {
                // 找到，则记录目标连续子数组的个数
                count += map.put(preSum - k, map.get(preSum - k));
            }
            // 记录当前前缀和出现的次数
            // 因为nums元素可能有负数
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }

    /**
     * 个解：滑动窗口-错误
     * <p>
     * 错误原因：滑动窗口移动不好控制
     */
    public int subarraySum(int[] nums, int k) {
        // nums元素可重复，且无序
        // 子数组需连续
        int start = 0, end = 0, windowSum = nums[start], count = 0;
        while (start < nums.length && end < nums.length) {
            if (windowSum < k) {
                end++;
                if (end < nums.length) {
                    windowSum += nums[end];
                }
            } else if (windowSum > k) {
                start++;
                if (start < nums.length) {
                    windowSum -= nums[start];
                }
            } else {
                // 找到，先记录
                count++;
                // 再右移start缩小窗口，从而找到新的连续子数组
                windowSum -= nums[start];
                start++;
//                if (start < nums.length) {
//                }
            }
        }

        return count;
    }

}
